<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40"><head>


<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="ProgId" content="Word.Document">
<meta name="Generator" content="Microsoft Word 9">
<meta name="Originator" content="Microsoft Word 9">
<link rel="Edit-Time-Data" href="http://uva.onlinejudge.org/external/100/p2_files/editdata.mso">
<link rel="OLE-Object-Data" href="http://uva.onlinejudge.org/external/100/p2_files/oledata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>Problem C - Playing with Wheels</title>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>Rezaul Alam Chowdhury</o:Author>
  <o:LastAuthor>Administrator</o:LastAuthor>
  <o:Revision>2</o:Revision>
  <o:TotalTime>302</o:TotalTime>
  <o:LastPrinted>1999-05-07T21:27:00Z</o:LastPrinted>
  <o:Created>2001-01-10T11:00:00Z</o:Created>
  <o:LastSaved>2001-01-10T11:00:00Z</o:LastSaved>
  <o:Pages>2</o:Pages>
  <o:Words>287</o:Words>
  <o:Characters>1637</o:Characters>
  <o:Company>CSE, BUET</o:Company>
  <o:Lines>13</o:Lines>
  <o:Paragraphs>3</o:Paragraphs>
  <o:CharactersWithSpaces>2010</o:CharactersWithSpaces>
  <o:Version>9.2720</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
  <w:DisplayVerticalDrawingGridEvery>0</w:DisplayVerticalDrawingGridEvery>
  <w:UseMarginsForDrawingGridOrigin/>
  <w:Compatibility>
   <w:FootnoteLayoutLikeWW8/>
   <w:ShapeLayoutLikeWW8/>
   <w:AlignTablesRowByRow/>
   <w:ForgetLastTabAlignment/>
   <w:LayoutRawTableWidth/>
   <w:LayoutTableRowsApart/>
  </w:Compatibility>
 </w:WordDocument>
</xml><![endif]-->
<style>
<!--
 /* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	color:black;}
strong
	{mso-bidi-font-weight:normal;}
em
	{mso-bidi-font-style:normal;}
p.Preformatted, li.Preformatted, div.Preformatted
	{mso-style-name:Preformatted;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:none;
	tab-stops:0in 47.95pt 95.9pt 143.85pt 191.8pt 239.75pt 287.7pt 335.65pt 383.6pt 431.55pt 479.5pt;
	layout-grid-mode:char;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";
	mso-bidi-font-family:"Times New Roman";}
p.DefinitionList, li.DefinitionList, div.DefinitionList
	{mso-style-name:"Definition List";
	mso-style-next:"Definition Term";
	margin-top:0in;
	margin-right:0in;
	margin-bottom:0in;
	margin-left:.25in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	layout-grid-mode:char;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.DefinitionTerm, li.DefinitionTerm, div.DefinitionTerm
	{mso-style-name:"Definition Term";
	mso-style-next:"Definition List";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	layout-grid-mode:char;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.H2, li.H2, div.H2
	{mso-style-name:H2;
	mso-style-next:Normal;
	margin-top:5.0pt;
	margin-right:0in;
	margin-bottom:5.0pt;
	margin-left:0in;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:3;
	layout-grid-mode:char;
	font-size:18.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	font-weight:bold;
	mso-bidi-font-weight:normal;}
p.Address, li.Address, div.Address
	{mso-style-name:Address;
	mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	layout-grid-mode:char;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	font-style:italic;
	mso-bidi-font-style:normal;}
@page Section1
	{size:8.5in 11.0in;
	margin:1.0in 1.25in 1.0in 1.25in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1029"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->
</head><body style="" lang="EN-US">

<div class="Section1">

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><font size="5">Problem C</font></b></p>


<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><font size="6">Playing with
Wheels</font></b></p>


<p class="MsoNormal" style="text-align: center;" align="center"><b>Input: </b>standard Input<b style=""><o:p></o:p></b></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b>Output: </b>standard output</p>

<p class="MsoNormal" style="text-align: justify;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">In this problem we
will be considering a game played with four wheels. Digits ranging from 0 to 9
are printed consecutively (clockwise) on the periphery of each wheel. The
topmost digits of the wheels form a four-digit integer. For example, in the
following figure the wheels form the integer 8056. Each wheel has two buttons
associated with it. Pressing the button marked with a <i style="">left arrow</i> rotates the wheel one digit in the clockwise direction
and pressing the one marked with the <i style="">right
arrow</i> rotates it by one digit in the opposite direction. </p>
<br>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="acm-10067_archivos/p10067.gif" height="251" width="571">
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify; text-indent: 0.5in;">The
game starts with an initial configuration of the wheels. Say, in the initial
configuration the topmost digits form the integer <b style=""><i style="">S</i><sub>1</sub><i style="">S</i><sub>2</sub><i style="">S</i><sub>3</sub><i style="">S</i><sub>4</sub></b>.
You will be given some (say, <b style=""><i style="">n</i></b>) forbidden configurations <b style=""><i style="">F<sub>i</sub></i><sub>1</sub><i style="">F<sub>i</sub></i><sub>2</sub><i style="">F<sub>i</sub></i><sub>3</sub><i style="">F<sub>i</sub></i><sub>4 </sub></b><span style="">&nbsp;</span>(1 &lt;= i &lt;= n ) and a target
configuration <b style=""><i style="">T</i><sub>1</sub><i style="">T</i><sub>2</sub><i style="">T</i><sub>3</sub><i style="">T</i><sub>4</sub></b>. Your job will be to write a program that can
calculate the minimum number of button presses required to transform the
initial configuration to the target configuration by never passing through a
forbidden one. </p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b style=""><font size="5">Input</font></b></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">The first line
of the input contains an integer <b style=""><i style="">N</i></b> giving the number of test cases to
follow. </p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify; text-indent: 0.5in;">The
first line of each test case contains the initial configuration of the wheels
specified by 4 digits. Two consecutive digits are separated by a space. The
next line contains the target configuration. The third line contains an integer
<b style=""><i style="">n</i></b>
giving the number of forbidden configurations. Each of the following <b style=""><i style="">n</i></b>
lines contains a forbidden configuration.</p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify; text-indent: 0.5in;">There
is a blank line between two consecutive input sets.</p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b style=""><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><o:p></o:p></b></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b style=""><font size="5">Output</font></b></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">For each test
case in the input print a line containing the minimum number of button presses
required. If the target configuration is not reachable then print -1.</p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b style=""><span style="font-size: 14pt;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></b></p>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b style=""><font size="5">Sample Input</font></b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;"><o:p></o:p></span></p>
<font size="3" face="Courier">

2<br>

8 0 5 6<br>

6 5 0 8<br>

5<br>

8 0 5 7<br>

8 0 4 7<br>

5 5 0 8<br>

7 5 0 8<br>

6 4 0 8<br>

<br>
0 0 0 0<br>

5 3 1 7<br>

8<br>

0 0 0 1<br>

0 0 0 9<br>

0 0 1 0<br>

0 0 9 0<br>

0 1 0 0<br>

0 9 0 0<br>

1 0 0 0<br>

9 0 0 0<br>
</font>

<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">
<font size="5"><b>Sample Output</b></font><b></b></p>
<font size="3" face="Courier">
14<br>
-1<br>
</font>
</div>
<font size="3" face="Times New Roman">
______________________________________________________________________________________
<br>Rezaul Alam Chowdhury
</font></body></html>